package br.uece.comp.paa.entity;

import java.util.LinkedList;
import java.util.List;

import br.uece.comp.paa.entity.grafo.Aresta;
import br.uece.comp.paa.entity.grafo.Grafo;

public class LasVegas extends GeradorArvoreMinima {

	List<List<Aresta>> lista = new LinkedList<List<Aresta>>();

	public final int LIMITE_INTERACOES_ARVORE;

	public static final int LIMITE_LISTA = 1;

	public static final int QTD_ITERACOES = 1000;

	public LasVegas(Grafo g) {
		super(g);
		LIMITE_INTERACOES_ARVORE = g.getNumeroVertices()
				* g.getNumeroVertices();
	}

	@Override
	public Grafo gerar(Grafo g, int grauMaximo, double custoMaximo) {

		boolean formouArvore = false;

		int verticeOrigem, verticeDestino;
		Double custo;
		List<Integer> verticesDentro = new LinkedList<Integer>();
		List<Integer> verticesFora = new LinkedList<Integer>();
		List<Aresta> arestas;

		for (int k = 0; k < QTD_ITERACOES; k++) {
			verticesDentro.clear();
			verticesFora.clear();
			arestas = new LinkedList<Aresta>();

			for (int v = 0; v < g.getNumeroVertices(); v++) {
				verticesFora.add(v + 1);
			}

			verticesDentro.add(sortearVertice(verticesFora));

			for (int i = 0; !formouArvore && i < LIMITE_INTERACOES_ARVORE; i++) {
				verticeOrigem = sortearVertice(verticesDentro);
				verticeDestino = sortearVertice(verticesFora);

				custo = g.getCusto(verticeOrigem - 1, verticeDestino - 1);
				if (custo != null) {
					if (respeitaRestricao(arestas, verticeOrigem - 1,
							grauMaximo)) {
						arestas.add(new Aresta(verticeOrigem - 1,
								verticeDestino - 1, custo));
						verticesDentro.add(verticeDestino);
						verticesFora.remove(new Integer(verticeDestino));

						if (verticesFora.size() == 0) {
							formouArvore = true;
						}
					} else {
						verticesDentro.remove(new Integer(verticeOrigem));
						i--;
					}
				} else {
					i--;
				}
			}

			atualizarLista(g, arestas);
			System.out.println("Interações: " + k);
			formouArvore = false;
		}

		return melhorSolucao(g);
	}

	private int sortearVertice(List<Integer> vertices) {
		int indice = (int) (Math.random() * vertices.size() - 1);

		return vertices.get(indice);
	}

	private void atualizarLista(Grafo gEntrada, List<Aresta> solucao) {
		if (lista.size() < LIMITE_LISTA) {
			lista.add(solucao);
		} else {
			Grafo g;
			Grafo gSolucao = gEntrada.extrairArvore(solucao);
			for (List<Aresta> elem : lista) {
				g = gEntrada.extrairArvore(elem);
				if (g.getCustoTotal() > gSolucao.getCustoTotal()) {
					lista.remove(elem);
					lista.add(solucao);
					break;
				}
			}
		}
	}

	private Grafo melhorSolucao(Grafo gEntrada) {
		List<Aresta> menor = lista.get(0);
		Grafo g1, g2;

		for (List<Aresta> a : lista) {
			g1 = gEntrada.extrairArvore(menor);
			g2 = gEntrada.extrairArvore(a);

			if (g1.getCustoTotal() > g2.getCustoTotal()) {
				menor = a;
			}
		}

		return gEntrada.extrairArvore(menor);
	}

	private boolean respeitaRestricao(List<Aresta> arestas, int vertice,
			int grauMaximo) {
		int grauAtual = 0;
		boolean resultado = true;

		if (grauMaximo == 0 || grauMaximo == 1) {
			return true;
		}

		for (Aresta aresta : arestas) {
			if (aresta.getVertice1() == vertice
					|| aresta.getVertice2() == vertice) {
				grauAtual++;
			}
		}

		if (grauAtual >= grauMaximo) {
			resultado = false;
		}

		return resultado;
	}
}
